On the Relative Expressiveness of Argumentation Frameworks, Normal Logic Programs and Abstract Dialectical Frameworks

摘要

We analyse the expressiveness of the two-valued semantics of abstractargumentation frameworks, normal logic programs and abstract dialecticalframeworks. By expressiveness we mean the ability to encode a desired set oftwo-valued interpretations over a given propositional signature using onlyatoms from that signature. While the computational complexity of the two-valuedmodel existence problem for all these languages is (almost) the same, we showthat the languages form a neat hierarchy with respect to their expressiveness.